package com.lw.leetcode.arr.b;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * arr
 * 923. 三数之和的多种可能
 *
 * @author liw
 * @version 1.0
 * @date 2022/1/19 22:42
 */
public class ThreeSumMulti {


    public static void main(String[] args) {
        ThreeSumMulti test = new ThreeSumMulti();

        // 20
//        int[] arr = {1,1,2,2,3,3,4,4,5,5};
//        int  target = 8;

        // 12
        int[] arr = {1, 1, 2, 2, 2, 2};
        int target = 5;

        int i = test.threeSumMulti(arr, target);
        System.out.println(i);
    }


    public int threeSumMulti(int[] arr, int target) {
        Arrays.sort(arr);
        List<Integer> values = new ArrayList<>();
        List<Integer> counts = new ArrayList<>();
        int item = -1;
        int count = 0;
        for (int i : arr) {
            if (i == item) {
                count++;
            } else {
                values.add(item);
                counts.add(count);
                item = i;
                count = 1;
            }
        }
        values.add(item);
        counts.add(count);
        Map<Integer, Integer> map = new HashMap<>();
        int size = values.size();
        for (int i = 1; i < size; i++) {
            map.put(values.get(i), i);
        }
        long sum = 0L;
        for (int i = 1; i < size; i++) {
            if (values.get(i) + values.get(i) + values.get(i) == target) {
                sum += (counts.get(i).longValue() * (counts.get(i) - 2) * (counts.get(i) - 1) / 6);
                break;
            }
            for (int j = i + 1; j < size; j++) {
                int v = target - values.get(i) - values.get(j);
                if (v == values.get(i)) {
                    sum += (counts.get(i).longValue() * counts.get(j) * (counts.get(i) - 1) / 2);
                } else if (v == values.get(j)) {
                    sum += (counts.get(i).longValue() * counts.get(j) * (counts.get(j) - 1) / 2);
                } else if (v > values.get(j)) {
                    Integer c = map.get(v);
                    if (c == null) {
                        continue;
                    }
                    sum += (counts.get(i).longValue() * counts.get(j) * counts.get(c));
                }
            }
            sum %= 1000000007;
        }
        sum %= 1000000007;
        return (int) sum;
    }
}
